The time required to search data can be shortened by giving an index to each piece of data that is a search target to constitute an index tree. Specifically, when searching for data, the index given to the data is searched from the index tree instead of directly searching for the data. The data can be acquired based on the index acquired as a search result.
The index tree is a data structure in tree structure in which nodes, each being a data structure including a plurality of entries, are connected. The entry is an index or an index level that is used to search for an index.
There are various types of index trees. For example, Non-Patent Documents 1 and 2 describe an index tree called B+-tree. Non-Patent Document 3 describes an index tree called T-tree. Non-Patent Document 4 describes an index tree called CSB+-tree.
Non-Patent Document 5 discloses a method using a single instruction multiple data instruction (SIMD instruction) for search of a node to which an index is given. The SIMD instruction is an instruction to execute the same processing in parallel for a plurality of pieces of data.
Non-Patent Document 6 discloses a method of rapidly performing search of an index using SIMD instructions. Specifically, in the above-described method, a sub-tree consisting of entries included within a node is formed within the node. Further, in the above-described method, a small tree consisting of entries included within the sub-tree is formed within the sub-tree. Also, in the above-described method, a size of the node is the same as a page size managed by an operating system (OS). Further, in the above-described method, a size of the sub-tree is set equal to a cache line size of a CPU. Furthermore, in the above-described method, the size of the small tree formed within the sub-tree is set equal to the number of pieces of data that can be targets of the SIMD instructions at one time.